package cn.edu.scau.cmi.huangxiyan.adapter;

import java.util.List;

public class SortUtil {

	public List<Integer> sortInt(List<Integer> intList) {
		sort(intList, 0, intList.size() - 1);

		return intList;
	}

	public void sort(List<Integer> intList, int p, int r) {
		int q = 0;

		if (p < r) {
			q = partition(intList, p, r);
			sort(intList, p, q - 1);
			sort(intList, q + 1, r);
		}
	}

	public int partition(List<Integer> intList, int p, int r) {
		int x = intList.get(r);
		int j = p - 1;

		for (int i = p; i <= r - 1; i++) {
			if (intList.get(i) <= x) {
				j++;
				swap(intList, j, i);
			}
		}

		swap(intList, j + 1, r);

		return j + 1;
	}

	public void swap(List<Integer> intList, int i, int j) {
		int temp = intList.get(i);

		intList.set(i, intList.get(j));
		intList.set(j, temp);
	}

}
